package com.wc.alorithm_luogu.P2196;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.LinkedList;

/**
 * @Author congge
 * @Date 2023/9/27 22:24
 * @description 挖地雷
 * https://www.luogu.com.cn/problem/P2196
 */
public class Main {
    public static void main(String[] args) {
        Input scan = new Input();

        int n = scan.nextInt();

        /**
         * 记录地窖中的雷数
         */
        int[] lights = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            lights[i] = scan.nextInt();
        }

        /**
         * combine[i][j] 表示i是否与j连接
         */
        int[][] combine = new int[n + 1][n + 1];

        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                combine[i][j] = scan.nextInt();
            }
        }

        /**
         * 存储到达当前的最大地雷数路径
         */
        LinkedList<LinkedList<Integer>> paths = new LinkedList<>();

        /**
         * 初始化所有当前地窖数目
         */
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = lights[i];
        }

        for (int i = 0; i <= n; i++) {
            LinkedList<Integer> curPath = new LinkedList<>();
            curPath.add(i);
            paths.add(curPath);
        }

        /**
         * 开始遍历每一个能到达自己地窖的地窖，计算出最大数
         */
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (combine[j][i] == 1) {
                    /**
                     * 能到达自己地窖，后比较之前的，再进行替换
                     */
                    if (dp[j] + lights[i] > dp[i]) {
                        dp[i] = dp[j] + lights[i];
                        LinkedList<Integer> curPath = paths.get(i);
                        LinkedList<Integer> prePath = paths.get(j);
                        /**
                         * 如果地窖里面只有自己的话，就将前面地窖的路径直接加入进来
                         * 否则就清空路径，加入前面的路径后再加自己的
                         */
                        if (curPath.size() == 1) {
                            curPath.addAll(0, prePath);
                        } else {
                            curPath.clear();
                            curPath.addAll(prePath);
                            curPath.add(i);
                        }
                    }
                }
            }
        }

        /**
         * 筛选出最大地雷数目，以及到达该地窖的路径
         */
        int max = dp[1];
        LinkedList<Integer> ansPath = paths.get(0);
        for (int i = 2; i <= n; i++) {
            if (max < dp[i]) {
                max = dp[i];
                ansPath = paths.get(i);
            }
        }

        int size = ansPath.size();
        for (int i = 0; i < size; i++) {
            System.out.printf("%s", i == size - 1 ? ansPath.get(i) : ansPath.get(i) + " ");
        }

        System.out.println("\n" + max);
    }

    static class Input {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public int nextInt() {
            try {
                in.nextToken();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return (int) in.nval;
        }
    }
}
